/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 adventure_path_finder.cpp

	$Header: /heroes4/adventure_path_finder.cpp $

	$NoKeywords: $

 ************************************************************************/
// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "adventure_path_finder.h"

#include <limits>
#include <stdlib.h>

#include "adventure_ai.h"
#include "adventure_map.h"
#include "angle.h"
#include "army.h"
#include "bound_handler.h"
#include "caravan.h"
#include "direction.h"
#include "enum_operations.h"
#include "path_step.h"
#include "player.h"

#include "profile.h"

namespace
{
	// The cost of a caravan moving through an enemy. Should be high enough to
	// ensure that caravans will ALWAYS prefer moving around an enemy
	unsigned int const k_caravan_enemy_move_cost = std::numeric_limits< unsigned int >::max() / 2;

	const float k_barrier_conversion_multiplier = 10.0f;
	const float k_danger_conversion_multiplier = 1500.0f;

	// ---------------------------------------------------------------
	// ---------------------------------------------------------------
	void copy_enemy_data( t_adventure_path_data const & source, t_adventure_path_data & dest )
	{
		dest.actual_enemy_adjacent = source.actual_enemy_adjacent;
		dest.actual_enemy_direction = source.actual_enemy_direction;
		dest.actual_enemy_distance = source.actual_enemy_distance;
		dest.actual_restricts_movement = source.actual_restricts_movement;
		dest.visible_enemy_adjacent = source.visible_enemy_adjacent;
		dest.visible_enemy_direction = source.visible_enemy_direction;
		dest.visible_enemy_distance = source.visible_enemy_distance;
		dest.visible_restricts_movement = source.visible_restricts_movement;
	}

	const t_uint16 k_path_data_version = 0;
	const t_uint16 k_path_version = 0;
	const t_uint16 k_path_point_version = 0;

	struct t_adventure_path_data_old
	{
		unsigned int			visited						: 1;  // if there's any way to reach this cell.
		t_direction				direction				    : 5;
		unsigned int            blocked_by_enemy		    : 1;  // Applies to type k_path_search_caravan ONLY
																  // To reach this point, we went through a
																  // hostile enemy & have already be charged
																  // for going through
		unsigned int			touched						: 1; 

		unsigned int			actual_enemy_adjacent		: 1;
		t_direction				actual_enemy_direction		: 5;
		unsigned int			actual_enemy_distance		: 5;
		unsigned int			enemy_restricts_movement	: 1;
		unsigned int			in_danger					: 1;
		unsigned int			visible_enemy_adjacent		: 1;
		t_direction				visible_enemy_direction		: 5;
		unsigned int			visible_enemy_distance		: 5;


		unsigned int			adjusted_move_cost;
		float					barrier_value;	
		t_creature_array const*	current_barrier;
		float					danger_value;
		t_adv_map_point			last_point;				// previous point in path.
		unsigned int			move_cost;				// cost in movement points to this point.
		unsigned int			move_remaining;
		t_army_path_state		pathing_state;
		float					value;

	};

	struct t_adventure_path_point_old : public t_adventure_path_data_old, public t_adv_map_point
	{
	};

	bool write_path_data( std::streambuf& buffer, t_adventure_path_data const& path_data )
	{
		put< t_uint16 >( buffer, k_path_data_version );

		put< t_direction >( buffer, path_data.direction );
		put< t_direction >( buffer, path_data.actual_enemy_direction );
		put< t_direction >( buffer, path_data.visible_enemy_direction );
		put< t_adv_map_point >( buffer, path_data.last_point );
		put< t_army_path_state >( buffer, path_data.pathing_state );
		put< float > ( buffer, path_data.barrier_value );
		put< float > ( buffer, path_data.danger_value );
		put< float > ( buffer, path_data.value );

		put< unsigned int >( buffer, path_data.visited );
		put< unsigned int >( buffer, path_data.blocked_by_enemy );
		put< unsigned int >( buffer, path_data.touched );
		put< unsigned int >( buffer, path_data.actual_enemy_adjacent );
		put< unsigned int >( buffer, path_data.actual_enemy_distance );
		put< unsigned int >( buffer, path_data.visible_restricts_movement );
		put< unsigned int >( buffer, path_data.in_danger );
		put< unsigned int >( buffer, path_data.visible_enemy_adjacent );
		put< unsigned int >( buffer, path_data.visible_enemy_distance );
		put< unsigned int >( buffer, path_data.adjusted_move_cost );
		put< unsigned int >( buffer, path_data.move_cost );
		put< unsigned int >( buffer, path_data.move_remaining );
		put< unsigned int >( buffer, path_data.step_count );

		return true;
	}

	bool read_path_data( std::streambuf& buffer, t_adventure_path_data& path_data )
	{
		t_uint16 path_data_version = get< t_uint16 >( buffer );

		path_data.direction = get< t_direction >( buffer );
		path_data.actual_enemy_direction = get< t_direction >( buffer );
		path_data.visible_enemy_direction = get< t_direction >( buffer );
		path_data.last_point = get< t_adv_map_point >( buffer );
		path_data.pathing_state = get< t_army_path_state >( buffer );
		path_data.barrier_value = get< float >( buffer );
		path_data.danger_value = get< float >( buffer );
		path_data.value = get< float >( buffer );
		path_data.current_barrier = NULL;

		path_data.visited = get< unsigned int >( buffer );
		path_data.blocked_by_enemy = get< unsigned int >( buffer );
		path_data.touched = get< unsigned int >( buffer );
		path_data.actual_enemy_adjacent = get< unsigned int >( buffer );
		path_data.actual_enemy_distance = get< unsigned int >( buffer );
		path_data.visible_restricts_movement = get< unsigned int >( buffer );
		path_data.in_danger = get< unsigned int >( buffer );
		path_data.visible_enemy_adjacent = get< unsigned int >( buffer );
		path_data.visible_enemy_distance = get< unsigned int >( buffer );
		path_data.adjusted_move_cost = get< unsigned int >( buffer );
		path_data.move_cost = get< unsigned int >( buffer );
		path_data.move_remaining = get< unsigned int >( buffer );
		path_data.step_count = get< unsigned int >( buffer );

		return true;
	}
}


t_army* find_restrictive_enemy( t_adventure_map&				map,
						        t_adventure_enemy_marker const&	path_finder, 
								t_adv_map_point					point, 
								t_creature_array const&			army,
								t_direction*					direction )
{
	t_adventure_path_data const* data = &path_finder.get_existing_data( point );

	if (data->visible_restricts_movement == false)
		return NULL;
	
	return find_enemy( map, path_finder, point, army, direction );
}	

t_army* find_enemy( t_adventure_map&				map,
						        t_adventure_enemy_marker const&	path_finder, 
								t_adv_map_point					point, 
								t_creature_array const&			army,
								t_direction*					direction )
{
	t_adventure_path_data const* data = &path_finder.get_existing_data( point );

	assert( army.get_stealth_level() == path_finder.get_army()->get_stealth_level() );
	if (data->actual_enemy_adjacent == false)
		return NULL;
	
	while( data->actual_enemy_distance > 0 )
	{
		if (direction != 0)
			*direction = data->actual_enemy_direction;

		if ( map.is_ramp_open( point, data->actual_enemy_direction ) )
			point.on_bridge = !point.on_bridge;

		point += get_direction_offset( data->actual_enemy_direction );

		t_adventure_tile const& tile = map[point];

		data = &path_finder.get_existing_data( point );		
	}

	if ( data->actual_enemy_distance == 0 )
	{
		t_adventure_tile const& tile = map.get_adv_tile(point);
		if (tile.is_trigger( point.on_bridge ) == false)
		{
			assert(false);
			return NULL;
		}	

		const std::vector<int>& triggers = tile.get_triggers(point.on_bridge);
		for (std::vector<int>::const_iterator iter = triggers.begin(); iter != triggers.end(); iter++)
		{
			t_adventure_object& trigger = map.get_adv_object(*iter);
			t_army* enemy_army = trigger.get_army();
			if ( enemy_army && !enemy_army->is_graveyard() && enemy_army->is_triggered_by(army) )
				return enemy_army;
		}
	}
	
	return NULL;
}	



// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
t_adventure_path_finder::t_adventure_path_finder( t_adventure_map& map )
                       : t_adventure_enemy_marker( map ),
						 m_patrol_distance(-1), m_patrol_array_size(-1),
						 m_visited_points( NULL ), m_can_summon_boat(false)
{
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
bool t_adventure_path_finder::can_summon_boat()
{
	if (m_summon_boat_checked)
		return m_can_summon_boat;
	if (m_path_type != k_path_search_ai)
		return false;

	m_summon_boat_checked = false;
	m_can_summon_boat = false;
  int i;
	for (i = 0; i < t_creature_array::k_size; i++)
	{
		t_hero* hero = (*m_army)[i].get_hero();

		if (hero && hero->can_cast( k_spell_summon_boat ))
			break;
	}
	if (i == t_creature_array::k_size)
		return false;

	if (m_map.has_empty_boat( *m_army->get_owner() ))
	{
		m_can_summon_boat = true;
		return true;
	}
	return false;
}


void t_adventure_path_finder::initialize()
{
	if ( m_initialized )
		return;
	if ( m_army == NULL )
		return;

	t_adventure_enemy_marker::initialize();

	m_can_summon_boat = false;
	m_summon_boat_checked = false;

	int patrol_radius = m_army->get_patrol_radius();

	if (m_path_type == k_path_search_player_danger)
	{
		if (m_army->get_patrol_type() == k_patrol_none
			|| patrol_radius > k_guard_maximum_radius)
			patrol_radius = k_guard_maximum_radius;
	}
	m_patrol_distance = patrol_radius + 1;
	m_patrol_array_size = m_patrol_distance * 2 + 1;

	if (m_army->get_army())
		m_starting_point = m_army->get_position();
	else
	{
		if (!m_army->get_virtual_position( m_starting_point )) 
		{
			return;
		}
	}

	t_adventure_path_point start( m_starting_point );

	int movement[2];

	movement[ false ] = m_army->get_movement( false );
	movement[ true ]  = m_army->get_movement( true );
	
	m_open_points = t_adventure_path_queue();

	bool is_boat = m_army->is_boat() || m_army->is_aquatic();

	start.danger_value = 0.0f;
	start.move_cost = 0;
	start.adjusted_move_cost = 0;
	start.current_barrier = NULL;
	start.danger_value = 0.0f;
	start.barrier_value = 0.0f;
	start.visited = true;
	start.touched = true;
	start.actual_enemy_adjacent = false;
	start.visible_enemy_adjacent = false;
	start.last_point.row = -1;
	start.last_point.column = -1;
	start.last_point.level = -1;
	start.pathing_state = is_boat ? k_army_path_state_ship : k_army_path_state_normal;
	start.move_remaining = movement[ is_boat ];
	start.blocked_by_enemy = false;
	start.step_count = 0;

	if (m_path_type == k_path_search_ai) 
	{
		start.current_barrier = find_enemy( m_map, *this, m_starting_point, *m_army );

		if (start.current_barrier)
		{
			float value = m_map.get_ai().get_cache().value_lost_in_combat( *m_army, *start.current_barrier );
			if (value > 0.0f) 
				start.danger_value = value;
		}
	} 

	t_adventure_path_data& data = m_data.get( start );

	copy_enemy_data( data, start );
	m_open_points.push( start );
	m_data.get( start ) = start;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
bool t_adventure_path_finder::push( t_path_step& step )
{
	t_adventure_path_data& old_point = m_data.get( step.new_point );

	if (old_point.visited)
	{
		if (old_point.adjusted_move_cost <= step.new_point.adjusted_move_cost)
			return false;
	}
	else if (m_visited_points != 0)
	{
		switch (m_path_type)
		{
			case k_path_search_ai_guarding_army:
				if (check_trigger( step ) != 0)
					m_visited_points->push_back( step.new_point );
				break;

			case k_path_search_player_danger:
				if (!old_point.touched)
					m_visited_points->push_back( step.new_point );
				break;

			case k_path_search_ai_threat:	
				if (!old_point.touched)
				{
					int delta_column;
					int delta_row;
					// Exclude the activation radius...  That's already part of the path.danger_value.
					// We'll keep pathing, but we'll exclude the point from the visited list.
					delta_column = step.new_point.column - m_starting_point.column + k_army_attack_radius;
					delta_row    = step.new_point.row - m_starting_point.row + k_army_attack_radius;
					if (delta_column < 0 || delta_column >= k_army_attack_array_size
						|| delta_row < 0 || delta_row >= k_army_attack_array_size)
						m_visited_points->push_back(step.new_point);
				}
				break;
			case k_path_search_ai_guard_danger:
			case k_path_search_ai_danger:
				if (!old_point.touched)
				{
					if (!old_point.actual_enemy_adjacent)
						m_visited_points->push_back(step.new_point);
				}
				break;
				
			default:
				m_visited_points->push_back(step.new_point);	
				break;
		}
	}

	copy_enemy_data( old_point, step.new_point );

	// Caravans can't get through activation radii
	if ( step.new_point.actual_enemy_adjacent && !step.new_point.blocked_by_enemy )
	{
		step.new_point.blocked_by_enemy = true;

		if( m_path_type == k_path_search_caravan )
		{
			// Note: k_caravan_enemy_move_cost is large enough to overflow if 
			// we add to the totals twice. Only charge once per path
			step.new_point.adjusted_move_cost += k_caravan_enemy_move_cost;
		}
	}
	assert( step.new_point.last_point == step.point );
	assert( step.point.column < 0 
		|| step.new_point.adjusted_move_cost >= m_data.get( step.point ).adjusted_move_cost );
	old_point = step.new_point;

	if (!step.new_point.visited)
		return false;
	m_open_points.push( step.new_point );
	return true;
}

// ---------------------------------------------------------------
// check if we should enter a blocked tile
// ---------------------------------------------------------------
bool t_adventure_path_finder::enter_blocked_tile( t_path_step& step )
{
	if (check_trigger( step ) != 0)
	{
		// if direction is not blocked, but the target cell is blocked, 
		// that means we have diagonal blockers and we shouldn't try
		// to enter the cell.
		if (!step.tile->blocks_army( *m_army, m_map, 
									 step.new_point.on_bridge, m_path_type ))
		{
			if (m_map.corners_block( step.point, step.new_point, step.direction ))
				return false;
		}
		return true;
	}

	// only danger searches enter blocked tiles that aren't triggers.
	if ( m_path_type != k_path_search_ai_danger 
		 && m_path_type != k_path_search_ai_guard_danger
		 && m_path_type != k_path_search_player_danger)
		 return false;
		
	if ( step.tile->blocks_army( *m_army, m_map, 
								 step.new_point.on_bridge, m_path_type ))
		return false;
	step.new_point.visited = false; // we don't want to visit this tile, but
									// we do want to mark it as touched.
	return true;
}

t_adventure_object* t_adventure_path_finder::check_trigger( t_path_step& step ) const
{
	if (!step.trigger_checked)
	{
		step.trigger_checked = true;
		step.trigger = m_map.get_trigger_object( step.point, step.direction, m_army );
	}
	return step.trigger;
}

bool t_adventure_path_finder::validate_water_step( t_path_step const& step ) const
{
	return true;
}

// ---------------------------------------------------------------
// check if this is a land / water transition
// ---------------------------------------------------------------
bool t_adventure_path_finder::check_water( t_path_step& step )
{
	if (step.point.pathing_state == k_army_path_state_ship)
	{
		// we're a ship.  check if we're landing.
		if ( m_map.is_land( step.new_point ))
		{
			// value searches don't extend from water to land.
			if (m_path_type == k_path_search_ai_value)
				return false;
			// boats can only enter land squares IF the we are landing OR trading/attacking.
			// last square must be water, and there can be nothing
			// in this square except another army.
			if ( check_trigger( step ) != 0 )
			{
				if (!step.trigger->is_actor())
					return false;
			}
			else
			{
				if ((m_path_type == k_path_search_ai_neutral_army)
					|| (m_path_type == k_path_search_ai_guarding_army))
					return false;
			}

			if (m_path_type == k_path_search_find_nearby_space)
				return false;

			// non-standard paths switch state from boat to water.  
			// standard ones keep their original information.
			if (m_path_type != k_path_search_standard
				&& m_path_type != k_path_search_enemy_activation
				&& m_path_type != k_path_search_ai_danger
				&& m_path_type != k_path_search_ai_guard_danger
				&& m_path_type != k_path_search_player_danger 
				&& m_path_type != k_path_search_ai_neutral_army
				&& m_path_type != k_path_search_ai_guarding_army)
				step.new_point.pathing_state = k_army_path_state_normal;
		}
		else if ( step.direction & 1 )
		{
			t_adv_map_point new_point;
			
			new_point = step.point + get_direction_offset( clockwise( step.direction ) );
			if (!m_map.is_valid( new_point ))
				return false;
			if (m_map.is_land( new_point ))
				return false;
			new_point = step.point + get_direction_offset( counter_clockwise( step.direction ));
			if (!m_map.is_valid( new_point ))
				return false;
			if (m_map.is_land( new_point ))
				return false;
		}
		return true;
	}

	// we're a land army.  If the new tile is land or bridge, we're OK.
	if ( step.new_point.on_bridge || m_map.is_land( step.new_point ) )
		return true;

	// danger searches do extend into water.
	if (m_path_type == k_path_search_ai_danger
		|| m_path_type == k_path_search_ai_guard_danger
		|| m_path_type == k_path_search_player_danger )
		return true;

	// nearby-space and caravan searches never switch to water from land.
	if ( m_path_type == k_path_search_find_nearby_space
		|| m_path_type == k_path_search_caravan )
		return false;

	if (check_trigger( step ) != 0)
	{
		if (step.trigger->is_boat())
		{
			// non-standard paths switch state from boat to water.  
			// standard ones keep their original information.
			if ( m_path_type != k_path_search_standard
				&& m_path_type != k_path_search_enemy_activation
				&& m_path_type != k_path_search_ai_neutral_army 
				&& m_path_type != k_path_search_ai_guarding_army)
				step.new_point.pathing_state = k_army_path_state_ship;
			return true;
		}
	}
	else 
	{
		if ((m_path_type == k_path_search_ai_neutral_army)
			|| (m_path_type == k_path_search_ai_guarding_army))
			return false;
	}

	// only AI searches can summon / build boats
	if (m_path_type != k_path_search_ai)
		return false;

	if (can_summon_boat())
		step.new_point.barrier_value = 1000.0f;
	else
	{
		if (!step.tile->ai_can_build_ship())
			return false;

		t_adventure_ai&	ai = m_map.get_ai();

		step.new_point.barrier_value = ai.get_ship_construction_barrier();
	}
	step.new_point.pathing_state = k_army_path_state_ship;
	return true;
}

// ----------------------------------------------------------------------------
// check if danger prevents further movement
// ----------------------------------------------------------------------------
bool t_adventure_path_finder::check_danger( t_path_step& step ) const
{
	// Add any new barrier value we incur while moving to the destination.
	t_creature_array const* new_barrier = find_enemy( m_map, *this, step.new_point, 
													  *m_army );

	step.new_point.danger_value = 0.0;

	if (new_barrier && new_barrier != step.point.current_barrier)
	{
		t_adventure_ai&	ai = m_map.get_ai();
		float			value = ai.get_cache().value_lost_in_combat( *m_army, *new_barrier );

		if (value > 0.0f) 
			step.new_point.danger_value += value; // Add barrier	
	}
	step.new_point.current_barrier = new_barrier;
	
	float map_danger_value = (*m_danger_map_ptr)[get_map_index( m_map, step.new_point )];

	step.new_point.in_danger = (map_danger_value > 0.0f) ? 1 : 0;
	if (step.point.in_danger == 0 && step.new_point.in_danger == 1)
	{
		step.new_point.move_remaining 
			= m_movement[ step.new_point.pathing_state == k_army_path_state_ship ];
	}
	if (check_trigger( step ) != 0)
	{
		step.new_point.danger_value += step.trigger->ai_activation_value_drop( *m_army );
	}

	if (step.new_point.move_cost >= step.point.move_remaining) 
	{
		if (step.new_point.in_danger 
				&& ( (step.trigger == 0) 
						|| (step.point.pathing_state != step.new_point.pathing_state) ) )
		{
			step.new_point.danger_value += map_danger_value;
		}
		step.new_point.move_remaining 
			= m_movement[ step.new_point.pathing_state == k_army_path_state_ship ];
	}
	else
	{
		step.new_point.move_remaining = step.point.move_remaining 
										- step.new_point.move_cost;
		if ( step.point.move_remaining <= 400 && step.new_point.in_danger)
		{
			step.new_point.danger_value += map_danger_value;
			step.new_point.move_remaining 
				= m_movement[ step.new_point.pathing_state == k_army_path_state_ship ];
		}
	}

	step.new_point.adjusted_move_cost 
		+= step.new_point.barrier_value * k_barrier_conversion_multiplier;
	step.new_point.adjusted_move_cost 
		+= step.new_point.danger_value * k_danger_conversion_multiplier;
	step.new_point.barrier_value += step.point.barrier_value;
	step.new_point.danger_value += step.point.danger_value;
	if ( step.new_point.danger_value >= 1.0f )
	{
		t_adventure_ai&			ai = m_map.get_ai();

		if ( !ai.impending_defeat() && !ai.ignore_pathing_danger())
			return false;
	}
	return true;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
void t_adventure_path_finder::search_to(	t_adv_map_point const*	destination,
											unsigned int			move_points,
											t_search_handler        handler)
{
	bool standard_pathing =   (m_path_type == k_path_search_standard 
							|| m_path_type == k_path_search_enemy_activation);
	bool ai_pathing = (m_path_type == k_path_search_ai);
	bool is_ship = m_army->is_boat() || m_army->is_aquatic();

	declare_timer( timer_1, "search to" );

	initialize();

	t_adventure_path_data* destination_tile = NULL;
	if (destination != NULL) 
	{
		destination_tile = &m_data.get( *destination );
		assert(destination_tile);
		if (destination_tile->visited)
			return;
		if (m_map[*destination].is_blocked( destination->on_bridge ) && m_map.get_trigger_object( *destination, m_army ) == 0)
			return;
	}

	bool					valid_point[k_direction_count];
	t_adv_map_point			adjacent_points[k_direction_count];
	bool					blocked[k_direction_count];
	int						move_costs[k_terrain_count];
	t_terrain_type			terrain;
	t_player*				owner = m_army->get_owner();
	int						team_number = owner ? owner->get_team() : -1;
	t_visited_adv_points	pending_points;
	t_adventure_ai&			ai = m_map.get_ai();
	t_path_step				step;
	
	m_movement[ false ] = m_army->get_max_movement( false );
	m_movement[ true ]  = m_army->get_max_movement( true );

	// get move costs for this army on various terrains
	// pre-calculated here because this function is relatively expensive
	for (terrain = t_terrain_type(0); terrain < k_terrain_count; enum_incr(terrain))
	{
		move_costs[terrain] = m_army->get_move_cost( terrain );
	}

	while (!m_open_points.empty())
	{
		if (destination_tile && destination_tile->visited)
			return;

		step.point = m_open_points.top();
		m_open_points.pop();

		t_adventure_path_data& point_data = m_data.get(step.point);

		if (step.point.adjusted_move_cost > point_data.adjusted_move_cost)
			continue;

		assert( step.point.last_point.column < 0
			    || step.point.adjusted_move_cost 
				   >= m_data.get( step.point.last_point ).adjusted_move_cost );

		step.point = t_adventure_path_point(step.point, point_data);

		if (!standard_pathing 
				&& (m_path_type != k_path_search_ai_neutral_army) 
				&& (m_path_type != k_path_search_ai_guarding_army) )
			is_ship = (step.point.pathing_state == k_army_path_state_ship);

		if (is_ship == (step.point.on_bridge || m_map.is_land( step.point )))
			continue;	// ships don't move off from land, and armies don't move across water.

		t_adventure_tile const& old_tile = m_map[step.point];

		if (old_tile.blocks_army( *m_army, m_map, step.point.on_bridge, m_path_type ))
			continue;

		// Store the points that exceed the move limit.  These points will be re-added to m_open_points
		// after the search.  This will allow the path finder to efficiently resume searching from the 
		// points where our move limit was hit (in subsequent calls to search_to.)
		if (move_points < step.point.move_cost) 
		{
			pending_points.push_back( step.point );
			continue;
		}

		bool stop = false;

		handler(step.point, stop);
		
		if (stop)
			return;
		
		find_blocked_directions( step.point, *m_army, is_ship, adjacent_points, blocked, 
			                     valid_point );
		for (step.direction = t_direction(0); step.direction < k_direction_count; 
		     enum_incr( step.direction ))
		{
			if (!valid_point[step.direction])
				continue;
			if ( m_path_type == k_path_search_standard 
				|| (m_path_type == k_path_search_ai_value && (step.point.step_count > 1)) )
			{
				// is there an enemy guarding the last square?
				if ( step.point.visible_restricts_movement 
					 && step.point.visible_enemy_direction != step.direction )
					continue;
			}

			step.new_point = t_adventure_path_point( adjacent_points[step.direction] );

			if ( !standard_pathing && m_starting_point == step.new_point)
				continue;

			step.trigger_checked = false;
			step.trigger = NULL;
			step.tile = &m_map[step.new_point];

			if (blocked[step.direction] && !enter_blocked_tile( step ))
				continue;
			
			step.new_point.current_barrier = NULL;
			step.new_point.in_danger = false;
			step.new_point.pathing_state = step.point.pathing_state;
			step.new_point.barrier_value = 0.0;
			step.new_point.adjusted_move_cost = 0.0;

			// check if we're entering / leaving a ship
			if (!check_water( step ))
				continue;

			if (step.new_point.on_bridge)
				step.new_point.move_cost = 75;
			else if (is_ship)
				step.new_point.move_cost = 100;
			else
			{
				step.new_point.move_cost = move_costs[step.tile->get_terrain()];
				if (old_tile.get_road_type() != k_road_none 
					&& step.tile->get_road_type() != k_road_none)
				{
					if (step.tile->get_road_type() == k_road_dirt)
						step.new_point.move_cost = 100;
					else
						step.new_point.move_cost = 75;
				}
			}

			if (step.direction & 1)
				step.new_point.move_cost += step.new_point.move_cost >> 1;

			// if we're moving to/from a boat, expend all movement.
			// note that enemy activation / standard paths don't change this flag.
			if (step.new_point.pathing_state != step.point.pathing_state)
				step.new_point.move_cost = step.point.move_remaining;
			if (m_path_type == k_path_search_ai)
			{
				if (!check_danger( step ))
					continue;
			}
			else
			{
				if (step.new_point.move_cost >= step.point.move_remaining) 
				{
					step.new_point.move_remaining 
						= m_movement[ step.new_point.pathing_state == k_army_path_state_ship ];
				}
				else
				{
					step.new_point.move_remaining = step.point.move_remaining 
													- step.new_point.move_cost;
				}
			}

			step.new_point.adjusted_move_cost += step.new_point.move_cost;
			step.new_point.adjusted_move_cost += step.point.adjusted_move_cost;
			step.new_point.visited = true;
			step.new_point.touched = true;
			step.new_point.move_cost += step.point.move_cost;
			step.new_point.last_point = step.point;
			step.new_point.direction = step.direction;
			step.new_point.blocked_by_enemy = step.point.blocked_by_enemy;
			step.new_point.step_count = step.point.step_count + 1;
			assert( step.new_point.adjusted_move_cost >= step.point.adjusted_move_cost );

			if ( standard_pathing )
			{
				push( step );
			}
			else
			{
				if ( validate_point( step.new_point ) && push( step ) )
				{
					if (check_trigger( step ) == 0) 
						continue;

					if ( m_path_type == k_path_search_ai_neutral_army 
						|| m_path_type == k_path_search_ai_guarding_army )
						continue;

					step.trigger->pathing_destination_query( step.new_point, *this );
				}
			}
		}
	}

	while (!pending_points.empty())
	{
		t_adv_map_point					point = pending_points.back();
		t_adventure_path_data const&	data = m_data.get( point );
		t_adventure_path_point			new_point( point, data );

		m_open_points.push( new_point );
		pending_points.pop_back();
	}
}

// --------------------------------------------------------------------------
// check if the current point should be allowed
// --------------------------------------------------------------------------
bool t_adventure_path_finder::validate_danger( t_adventure_path_point const& point )
{
	if (m_army->get_owner() != NULL && !m_army->get_owner()->is_computer()) 
		return true;

	t_patrol_type type = m_army->get_patrol_type();

	if (type == k_patrol_none && m_path_type != k_path_search_player_danger)
		return true;

	if (type == k_patrol_guard)
	{
		if ( point.level != m_starting_point.level || point.step_count > m_patrol_distance )
			return false;
		return true;
	}

	int delta_column, delta_row;

	delta_column = point.column - m_starting_point.column + m_patrol_distance;
	delta_row = point.row - m_starting_point.row + m_patrol_distance;

	if (delta_column < 0 || delta_column >= m_patrol_array_size
		|| delta_row < 0 || delta_row >= m_patrol_array_size)

		return false;

	// If both this point and the last point are in the edge of the patrol radius, don't 
	// visit this location.  
	if ( delta_column == 0 || delta_row == 0 
		 || delta_column == m_patrol_array_size - 1 
		 || delta_row == m_patrol_array_size - 1 )
	{
		delta_column = point.last_point.column - m_starting_point.column + m_patrol_distance;
		delta_row = point.last_point.row - m_starting_point.row + m_patrol_distance;

		if ( delta_column == 0 || delta_row == 0 
			|| delta_column == m_patrol_array_size - 1 
			|| delta_row == m_patrol_array_size - 1 )
			return false;
	} 
	return true;
}

// --------------------------------------------------------------------------
// check if the current point should be allowed
// --------------------------------------------------------------------------
bool t_adventure_path_finder::validate_point( t_adventure_path_point const& point )
{
	switch (m_path_type)
	{
		case k_path_search_ai_guarding_army:
			if ( point.level != m_starting_point.level || point.step_count > m_patrol_distance )
				return false;
			return true;

		case k_path_search_ai_danger:
		case k_path_search_ai_guard_danger:
		case k_path_search_ai_threat:	
		case k_path_search_player_danger:
			return validate_danger( point );
		
		case k_path_search_ai_value:
			if ( point.level != m_starting_point.level || point.step_count > 2 )
				return false;
			return true;

		case k_path_search_ai_neutral_army:
		case k_path_search_ai:
		case k_path_search_ai_distance:
			if (m_army->get_patrol_type() != k_patrol_none)
			{
				int delta_column, delta_row;

				delta_column = point.column - m_starting_point.column + m_patrol_distance;
				delta_row = point.row - m_starting_point.row + m_patrol_distance;

				if (delta_column < 0 || delta_column >= m_patrol_array_size
					|| delta_row < 0 || delta_row >= m_patrol_array_size)
					return false;
			}
			return true;
	}
	return true;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
t_adventure_path_data const& t_adventure_path_finder::get_data( t_adv_map_point const& point )
{
	search_to( &point, std::numeric_limits<unsigned int>::max(), t_search_handler() );
	return m_data.get( point );
}


// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
bool t_adventure_path_finder::get_path( t_adv_map_point point, t_adventure_path& path, unsigned int move_points )
{
	search_to( &point, move_points, NULL );
	path.clear();

	if (!m_data.point_exists( point ))
		return false;

	t_adventure_path_data data = m_data.get( point );

	if ( !data.visited )
		return false;

	while (data.last_point.column >= 0)
	{
		path.push_back( t_adventure_path_point( point, data ) );
		assert( data.last_point != point );
		if (data.last_point == point)
			return false;
		point = data.last_point;
		
		t_adventure_path_data const& next_point = m_data.get( point );

		assert( next_point.move_cost <= data.move_cost );
		data = next_point;
	}
	return path.size() > 0;
}

// ---------------------------------------------------------------
// class to find paths for adventure map
// ---------------------------------------------------------------
void t_adventure_path_finder::seed_position( t_visited_adv_points& visited_points, unsigned int move_points )
{
	assert( m_visited_points == 0 );
	m_visited_points = &visited_points;
	search_to( NULL, move_points, t_search_handler() );
	m_visited_points = 0;
}

// ---------------------------------------------------------------
// Search until some external criteria is met
// ---------------------------------------------------------------
void t_adventure_path_finder::handler_based_search( t_search_handler handler )
{
	search_to( NULL, std::numeric_limits<unsigned int>::max(), handler );
}

// ---------------------------------------------------------------
// Public push function
// ---------------------------------------------------------------
bool t_adventure_path_finder::push( t_adv_map_point const&        point,
								    t_adventure_path_point const& prev_point,
									unsigned int				  move_cost,
									unsigned int				  additional_adjusted_move_cost,
									float                         barrier_value,
									t_army_path_state			  new_path_state )
{
	initialize();

	t_path_step step;

	step.new_point = t_adventure_path_point(point, prev_point);
	step.point = prev_point;

	if ( new_path_state == k_army_path_state_previous )
	{
		new_path_state = prev_point.pathing_state;
	}
	else if ( new_path_state == k_army_path_state_as_needed )
	{
		new_path_state = m_map.is_ocean( point ) 
			? k_army_path_state_ship : k_army_path_state_normal;
	}

	unsigned int adjusted_move_cost = move_cost + additional_adjusted_move_cost;
	

	step.new_point.move_cost = prev_point.move_cost + move_cost;
	step.new_point.barrier_value = prev_point.barrier_value + barrier_value;
	step.new_point.adjusted_move_cost = prev_point.adjusted_move_cost + adjusted_move_cost + barrier_value * k_barrier_conversion_multiplier;
	step.new_point.visited = true;
	step.new_point.touched = true;
	step.new_point.last_point = prev_point;
	step.new_point.direction = get_direction( get_angle( point - prev_point ) );
	step.new_point.pathing_state = new_path_state;
	step.new_point.step_count = prev_point.step_count + 1;
	step.direction = step.new_point.direction;
	step.trigger_checked = true;
	step.trigger = 0;
	
	if ( move_cost >= prev_point.move_remaining )
	{
		step.new_point.move_remaining = m_army->get_max_movement( new_path_state == k_army_path_state_ship );
	}
	else
	{
		step.new_point.move_remaining = prev_point.move_remaining - move_cost;
	}

	if (m_path_type == k_path_search_ai) 
	{
		t_creature_array const* new_barrier = find_enemy( m_map, *this, step.new_point, *m_army );

		if (new_barrier != prev_point.current_barrier)
		{
			if (new_barrier)
			{
				float value = m_map.get_ai().get_cache().value_lost_in_combat( *m_army, *new_barrier );
				if (value > 0.0f) 
					step.new_point.danger_value += value; // Add barrier	
			}
		}
		step.new_point.current_barrier = new_barrier;
	}

	if ( validate_point( step.new_point ) )
		return push( step );

	return false;
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_adventure_path_point::read( std::streambuf & buffer )
{
	t_uint16 point_version = get< t_uint16 >( buffer );

	t_adv_map_point* this_point = dynamic_cast<t_adv_map_point*>(this);
	assert(this_point != NULL);
	*this_point = get< t_adv_map_point >( buffer );;
	return read_path_data( buffer, *this );
}

// ---------------------------------------------------------------
// ---------------------------------------------------------------
bool t_adventure_path_point::write( std::streambuf & buffer ) const
{
	put< t_uint16 >( buffer, k_path_point_version );
	put< t_adv_map_point >( buffer, *this );
	return write_path_data( buffer, *this );
}

// ---------------------------------------------------------------
// read : reads in adventure paths
// ---------------------------------------------------------------
bool t_adventure_path::read( std::streambuf& buffer )
{
	int path_version = get< t_uint16 >( buffer );

	if (path_version < 0 || path_version > k_path_version)
		return false;

	return read( buffer, path_version );
}

// ---------------------------------------------------------------
// read : reads in adventure paths
// ---------------------------------------------------------------
bool t_adventure_path::read( std::streambuf & buffer, int path_version )
{
	int size = get<t_uint32> (buffer);

	if (path_version == -1)
	{
		clear();
		for (int i = 0; i < size; i++)
		{
			t_adventure_path_point_old path_point_old = get<t_adventure_path_point_old> (buffer);
			t_adventure_path_point point;
			t_adv_map_point* point_ptr = dynamic_cast< t_adv_map_point* >( &point );
			assert(point_ptr != NULL);
			*point_ptr = path_point_old;

			point.visited = path_point_old.visited;
			point.direction = path_point_old.direction;
			point.blocked_by_enemy = path_point_old.blocked_by_enemy;
			point.touched = path_point_old.touched;
			point.actual_enemy_adjacent = path_point_old.actual_enemy_adjacent;
			point.actual_enemy_direction = path_point_old.actual_enemy_direction;
			point.actual_enemy_distance = path_point_old.actual_enemy_distance;
			point.visible_restricts_movement = path_point_old.enemy_restricts_movement;
			point.in_danger = path_point_old.in_danger;
			point.visible_enemy_adjacent = path_point_old.visible_enemy_adjacent;
			point.visible_enemy_direction = path_point_old.visible_enemy_direction;
			point.visible_enemy_distance = path_point_old.visible_enemy_distance;
		
			point.adjusted_move_cost = path_point_old.adjusted_move_cost;
			point.barrier_value = path_point_old.barrier_value;
			point.current_barrier = path_point_old.current_barrier;
			point.danger_value = path_point_old.danger_value;
			point.last_point = path_point_old.last_point;
			point.move_cost = path_point_old.move_cost;
			point.move_remaining = path_point_old.move_remaining;
			point.pathing_state = path_point_old.pathing_state;
			point.value = path_point_old.value;
			point.step_count = 0;
			
			push_back(point);
		}
	}
	else
	{
		resize( size );
		for (int i = 0; i < size; i++)
			if (! ((*this)[i].read( buffer )) )
				return false;
	}

	return true;
}


// ---------------------------------------------------------------
// write : writes out adventure paths
// ---------------------------------------------------------------
bool t_adventure_path::write( std::streambuf & buffer ) const
{
	put<t_uint16>( buffer, k_path_version );
	put<t_uint32>( buffer, size() );

	std::vector<t_adventure_path_point>::const_iterator	 
		iter = begin(),
		iter_end = end();

	while (iter != iter_end)
	{
		if (! ((iter++)->write( buffer )) )
			return false;
	}

	return true;
}


namespace
{
	// Helper for start_object_adjacent_pathfind; pushes all points adjacent to
	// object onto the pathfinder
	class t_adjacent_point_pusher 
	{
		public:
			t_adjacent_point_pusher();

			bool push( t_adventure_path_finder & pathfinder, t_adventure_object const & object,
					   t_creature_array & army, t_place_army_handler place_army_handler);
			
		private:
			t_creature_array        * m_army;
			bool					  m_army_placed;
			t_adventure_map			* m_map;
			t_adventure_path_finder * m_pathfinder;
			t_place_army_handler      m_place_army_handler;
			t_adventure_path_point    m_starting_point;
		

			void scanner( t_adv_map_point const & point, t_adv_map_point const & trigger_cell, bool & stop );										
	};

	t_adjacent_point_pusher::t_adjacent_point_pusher()
		: m_pathfinder( NULL )
	{
	}

	// Starting point
	bool t_adjacent_point_pusher::push( t_adventure_path_finder & pathfinder, t_adventure_object const & object,
									    t_creature_array & army, t_place_army_handler place_army_handler )
	{
		m_pathfinder = &pathfinder;
		m_army = &army;
		m_place_army_handler = place_army_handler;
		m_army_placed = false;
		m_map = pathfinder.get_map();

		t_adventure_object::t_scan_adjacent_space_handler handler = bound_handler( *this, &t_adjacent_point_pusher::scanner );
		t_adv_map_point junk;

		object.scan_adjacent_spaces( handler, junk );

		return m_army_placed;
	}

	// Callback function
	void t_adjacent_point_pusher::scanner( t_adv_map_point const & point, t_adv_map_point const & trigger_cell, bool & stop )
	{
		// Never stop
		stop = false;

		if ( !m_map->is_valid( trigger_cell ) )
			return;

		if ( !m_army_placed )
		{
			// Must place army before calling set_army()
			// Must call set_army() before calling push()
			// Thus all the weird callback stuff
			m_place_army_handler( trigger_cell );
			m_pathfinder->set_army( m_army );
			m_starting_point = t_adventure_path_point( trigger_cell, m_pathfinder->get_data( trigger_cell ) );
			m_army_placed = true;
		}

		bool trigger_is_land = m_map->is_land( trigger_cell );

		if ( m_map->is_valid( point ) && ( m_map->is_land( point ) == trigger_is_land ) )
		{
			m_pathfinder->push( point, m_starting_point, 0, 0, 0.0, k_army_path_state_as_needed );
		}
	}
}


// ---------------------------------------------------------------
// Set up pathfinder so that all the points adjacent to 
// object are legit points to begin pathfinding from. 
// ---------------------------------------------------------------
bool start_object_adjacent_pathfind( t_adventure_path_finder & pathfinder, 
									 t_adventure_object const & object,
									 t_creature_array & army,
									 t_path_search_type search_type,
									 t_place_army_handler place_army_handler )
{
	pathfinder.clear();

	pathfinder.set_path_type( search_type );

	t_adjacent_point_pusher pusher;

	return pusher.push( pathfinder, object, army, place_army_handler );
}

